'''
快速排序
'''
from test57_class_stack import MyStack
from test24random_list import sjlb


def partition(ints, l, r):
    '''
    以整型列表第一个数为基准, 小于的放左边, 大于的放右边,等于放中间
    :param l,r: 需要排序的列表所有下标
    '''
    print(l, r)
    # 获取列表第一个作为基准
    v = ints[l]
    # m为小于等于区(以v为基准)右边界
    m = l
    for i in range(l, r + 1):
        if ints[i] < v:
            m += 1
            ints[i], ints[m] = ints[m], ints[i]
            # print(ints)
        s[0] += 1
    ints[l], ints[m] = ints[m], ints[l]
    llist = [l, m - 1]
    # 对于m处于r位置,也就是最大值在最右侧,不能让m+1了,否则越界
    #     # 需要做-1处理,这样返回的[左,右]左=右, 不用放入栈中
    if m + 1 > r:
        m -= 1
    rlist = [m + 1, r]
    return llist, rlist


def quick_sort(ints):
    count = 0
    if ints is None or len(ints) <= 1:
        return
        # 用于保存数组,数组里存放的是需要排序的数组左右边界下标
    stack = MyStack()
    rl = partition(ints, 0, len(ints) - 1)
    stack.push(rl[0])
    stack.push(rl[1])
    while stack.length > 0:
        l = stack.pop()
        ll, rl = partition(ints, l[0], l[1])
        if ll[0] < ll[1]:
            stack.push(ll)
        if rl[0] < rl[1]:
            stack.push(rl)


if __name__ == '__main__':
    s = [0]
    int_list = sjlb(10000, 10000000)
    int_list = [5,4,5,3,4,9,1,8]
    partition(int_list, 0, len(int_list)-1 )
    print(int_list)
    quick_sort(int_list)
    print(s, s[0] / len(int_list))
    print(int_list)
